/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* BuyNewNode(int data)
{
	struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
	tmp->val = data;
	tmp->next = NULL;
	if (tmp == NULL)
	{
		printf("开辟空间失败!");
		return;
	}
	else
	{
		return tmp;
	}
}
struct ListNode* SListinit()
{
	struct ListNode* tmp = (struct ListNode*)malloc(sizeof(struct ListNode));
	tmp->next = NULL;
	return tmp;
}
void SListPushBack(struct ListNode** List,int x)
{
	if (*List == NULL)
	{
		*List = SListinit();
		(*List)->val = x;
		return;
	}
	else
	{
		struct ListNode* tail = *List;
		struct ListNode* tmp = BuyNewNode(x);
		if (tmp == NULL)
		{
			printf("开辟空间失败!");
			return;
		}
		while(tail->next)
		{
			tail = tail->next;
		}
		tail->next = tmp;
	}
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* alpha = list1;
    struct ListNode* beta = list2;
    if(alpha == NULL && beta == NULL)
    {
        return list1;
    }
    while(alpha == NULL &&beta != NULL)
    {
        SListPushBack(&list1,alpha->val);
        alpha=alpha->next;
    }
    while(alpha && beta!=NULL)
    {
        if(alpha->val == beta->val)
        {
            SListPushBack(&list1,alpha->val);
            SListPushBack(&list1,beta->val);
            alpha=alpha->next;
            alpha=beta->next;
        }
        else if(alpha->val < beta->val)
        {
            SListPushBack(&list1,beta->val);
            alpha=alpha->next;
        }
        else if(alpha->val < beta->val)
        {
            SListPushBack(&list1,beta->val);
            beta= beta->next;
        }
    }
    while(alpha)
    {
        SListPushBack(&list1,alpha->val);
        alpha=alpha->next;
    }
    while(beta)
    {
        SListPushBack(&list1,alpha->val);
        beta=beta->next;
    }
    return list1;
}